package com.mj;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

import com.mj.BinarySearchTree.Visitor;
import com.mj.BinaryTree.Node;
import com.mj.printer.BinaryTreeInfo;

public class BinaryTreeLeetCode implements BinaryTreeInfo {
	protected int size;
	protected Node root;

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public void clear() {
		root = null;
		size = 0;
	}


	public int height() {
		int levelSize = 1;
		int height = 0;
		Queue<Node> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			Node node = queue.poll();
			levelSize--;
			if (node.left != null) {
				queue.offer(node.left);
			}
			if (node.right != null) {
				queue.offer(node.right);
			}
			if (levelSize == 0) {
				height ++;
				levelSize = queue.size();
			}
		}
		return height;
	}



	public static class Node {
		public Integer element;
		public Node left;
		public Node right;
		public Node parent;
		public Node(Integer element, Node parent) {
			this.element = element;
			this.parent = parent;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public boolean hasTwoChildren() {
			return left != null && right != null;
		}
	}

	@Override
	public Object root() {
		// TODO Auto-generated method stub
		return root;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object left(Object node) {
		// TODO Auto-generated method stub
		return ((Node)node).left;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object right(Object node) {
		// TODO Auto-generated method stub
		return ((Node)node).right;
	}

	@SuppressWarnings("unchecked")
	@Override
	public Object string(Object node) {
		// TODO Auto-generated method stub
		return ((Node)node).element;
	}
}
